package listbyorder.access001_100.test91;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/5 15:14
 */
public class Solution2 {

    // 方法二： 动态规划进行优化
    public int numDecodings(String s) {
        if (s == null || s.equals("")) return 0;
        int len = s.length();
        int[] dp = new int[len + 1];
        dp[len] = 1;
        dp[len - 1] = s.charAt(len - 1) == '0' ? 0 : 1;
        for (int i = len - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                dp[i] = 0;
            } else {
                int n1 = s.charAt(i) - '0';
                int n2 = s.charAt(i + 1) - '0';
                if (n1 * 10 + n2 < 27) {
                    dp[i] = dp[i + 1] + dp[i + 2];
                } else {
                    dp[i] = dp[i + 1];
                }
            }
        }
        return dp[0];
    }

}
